bool CompareAndSwap(void **target, void *oldval, void *newval);

// [[ex06bc]]
// DEBUG descr Lock-free stack.
class stack 
{
public: 
	struct node {
		node * volatile next_;
		int payload_; // the payload may be of any type
	};

	stack() : head_(0)
	{ }

	~stack()
	{
		while (pop() != 0) { }
	}

	void push(node *n)
	{
		node *old_head;
		do {
			old_head = head_;
			n->next_ = old_head;
		} while ( !CompareAndSwap(
				(void **)&head_, old_head, n) );
	}

	node *pop()
	{
		node *top, *newtop;
		do {
			top = head_;
			if (top == 0)
				return 0;
			newtop = top->next_;
		} while ( !CompareAndSwap(
				(void **)&head_, top, newtop) );
		return top;
	}

protected:
	// the head of the list, representing the top of stack
	node * volatile head_;
};
// END
